"""
计数排序: O(n+k)
基本思想：
    找出待排序的数组中最大和最小的元素；
    统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
    对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
    反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。
"""
import random


def counting_sort(seq):
    if not seq:
        return []
    seq_len = len(seq)   # 长度
    seq_min = min(seq)   # 最小值
    seq_max = max(seq)   # 最大值
    counting_arr_length = seq_max - seq_min + 1
    counting_arr = [0] * counting_arr_length   # 生成列表
    for number in seq:
        counting_arr[number-seq_min] += 1
    for i in range(1, counting_arr_length):
        counting_arr[i] = counting_arr[i] + counting_arr[i-1]
    ordered = [0] * seq_len

    for i in range(seq_len-1, -1, -1):
        ordered[counting_arr[seq[i] - seq_min] - 1] = seq[i]
        counting_arr[seq[i] - seq_min] -= 1
    return ordered


if __name__ == '__main__':
    sequence = [random.randint(1, 10000) for i in range(500)]
    print(sequence)
    print(counting_sort(sequence))

